{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Path Sum II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #backtracking #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #回溯 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: pathSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #路径总和 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你二叉树的根节点 <code>root</code> 和一个整数目标和 <code>targetSum</code> ，找出所有 <strong>从根节点到叶子节点</strong> 路径总和等于给定目标和的路径。</p>\n",
    "\n",
    "<p><strong>叶子节点</strong> 是指没有子节点的节点。</p>\n",
    "\n",
    "<div class=\"original__bRMd\">\n",
    "<div>\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/01/18/pathsumii1.jpg\" style=\"width: 500px; height: 356px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22\n",
    "<strong>输出：</strong>[[5,4,11,2],[5,8,4,5]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/01/18/pathsum2.jpg\" style=\"width: 212px; height: 181px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2,3], targetSum = 5\n",
    "<strong>输出：</strong>[]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2], targetSum = 0\n",
    "<strong>输出：</strong>[]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点总数在范围 <code>[0, 5000]</code> 内</li>\n",
    "\t<li><code>-1000 <= Node.val <= 1000</code></li>\n",
    "\t<li><code>-1000 <= targetSum <= 1000</code></li>\n",
    "</ul>\n",
    "</div>\n",
    "</div>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [path-sum-ii](https://leetcode.cn/problems/path-sum-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [path-sum-ii](https://leetcode.cn/problems/path-sum-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,4,8,11,null,13,4,7,2,null,null,5,1]\\n22', '[1,2,3]\\n5', '[1,2]\\n0']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, tot: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        if not root:\n",
    "            return ans\n",
    "        \n",
    "        def getPath(node, path):\n",
    "            if node:\n",
    "                if not node.left and not node.right:\n",
    "                    if sum(path) + node.val == tot:\n",
    "                        ans.append(path + [node.val])\n",
    "                else:\n",
    "                    getPath(node.left, path+[node.val])\n",
    "                    getPath(node.right, path+[node.val])\n",
    "                    \n",
    "        getPath(root, [])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def pathSum(self, root, sum1):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type sum: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        if root==None:\n",
    "            return []\n",
    "        stack,res=[(root,[root.val])],[]\n",
    "        while stack:\n",
    "            temp,val=stack.pop()\n",
    "            if not temp.left and not temp.right:\n",
    "                if sum(val)==sum1:\n",
    "                    res.append(val)\n",
    "            if temp.left:\n",
    "                stack.append((temp.left,val+[temp.left.val]))\n",
    "            if temp.right:\n",
    "                stack.append((temp.right,val+[temp.right.val]))\n",
    "        return res      \n",
    "            \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def search(self, root, sum, tempResult, result):\n",
    "        if not root.left and not root.right:\n",
    "            if sum-root.val != 0:\n",
    "                return\n",
    "            else:\n",
    "                temp = [val for val in tempResult]\n",
    "                temp.append(root.val)\n",
    "                result.append(temp)\n",
    "                return\n",
    "        if root.left:\n",
    "            tempResult.append(root.val)\n",
    "            self.search(root.left, sum-root.val, tempResult, result)\n",
    "            tempResult.pop()   \n",
    "        if root.right:\n",
    "            tempResult.append(root.val)\n",
    "            self.search(root.right, sum-root.val, tempResult, result)\n",
    "            tempResult.pop()\n",
    "            \n",
    "        \n",
    "    def pathSum(self, root, sum):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type sum: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        tempResult = []\n",
    "        result = []\n",
    "        if not root:\n",
    "            return result\n",
    "        self.search(root, sum, tempResult, result)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root, sum):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type sum: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        def dfs(res, stack, cursum, node, target):\n",
    "            if not node:\n",
    "                return res\n",
    "            cursum += node.val\n",
    "            stack.append(node.val)\n",
    "            if not node.left and not node.right and cursum == target:\n",
    "                res.append(stack[:])\n",
    "            res = dfs(res, stack, cursum, node.left, target)\n",
    "            res = dfs(res, stack, cursum, node.right, target)\n",
    "            stack.pop()\n",
    "            return res\n",
    "        return dfs([], [], 0, root, sum)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root, sum_):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type sum: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        \n",
    "        def getpaths(root):\n",
    "            if not root: return None\n",
    "            if not root.left and not root.right: return [[root.val]]\n",
    "            lft = getpaths(root.left)\n",
    "            rht = getpaths(root.right)\n",
    "            res = []\n",
    "            if lft:\n",
    "                for x in lft: x.append(root.val)\n",
    "                res.extend(lft)\n",
    "            if rht:\n",
    "                for x in rht: x.append(root.val)\n",
    "                res.extend(rht)\n",
    "            return res\n",
    "        \n",
    "        \n",
    "        res = []\n",
    "        if not root: return res\n",
    "        \n",
    "        for x in getpaths(root):\n",
    "            if sum(x) == sum_:\n",
    "                res.append(x[::-1])\n",
    "        \n",
    "        return res\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def pathSum(self, root, sum1):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type sum: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        if root==None:\n",
    "            return []\n",
    "        stack=[(root,[root.val])]\n",
    "        res=[]\n",
    "        while stack:\n",
    "            root,onepath=stack.pop()\n",
    "            print(sum(onepath))\n",
    "            if sum(onepath)==sum1 and root.left==None and root.right==None:\n",
    "                res.append(onepath)\n",
    "            if root.right:\n",
    "                stack.append((root.right,onepath+[root.right.val]))\n",
    "            if root.left:\n",
    "                stack.append((root.left,onepath+[root.left.val]))\n",
    "        return res\n",
    "        # stack,res=[(root,[root.val])],[]\n",
    "        # while stack:\n",
    "        #     temp,val=stack.pop()\n",
    "        #     if not temp.left and not temp.right:\n",
    "        #         if sum(val)==sum1:\n",
    "        #             res.append(val)\n",
    "        #     if temp.left:\n",
    "        #         stack.append((temp.left,val+[temp.left.val]))\n",
    "        #     if temp.right:\n",
    "        #         stack.append((temp.right,val+[temp.right.val]))\n",
    "        # return res\n",
    "                \n",
    "            \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "\n",
    "        res = []                 \n",
    "        temp = []             \n",
    "\n",
    "        def getPath(node,nowNum):\n",
    "            if not node:\n",
    "                return\n",
    "\n",
    "            nowNum += node.val\n",
    "            temp.append(node.val)\n",
    "\n",
    "            if not node.left and not node.right and nowNum==sum:\n",
    "                res.append(temp.copy())\n",
    "                temp.pop()\n",
    "                return\n",
    "\n",
    "            getPath(node.left,nowNum)\n",
    "            getPath(node.right,nowNum)\n",
    "            temp.pop()\n",
    "\n",
    "        getPath(root,0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root, sum):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type sum: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return []\n",
    "        self.ans=[]\n",
    "        self.dfs(root,sum,[])\n",
    "        return self.ans\n",
    "    def dfs(self,p,sum,tmp):\n",
    "        if p is None and sum==0:\n",
    "            self.ans.append(tmp)\n",
    "        elif not p:\n",
    "            return\n",
    "        elif not p.left:\n",
    "            self.dfs(p.right,sum-p.val,tmp+[p.val])\n",
    "        elif not p.right:\n",
    "            self.dfs(p.left,sum-p.val,tmp+[p.val])\n",
    "        else:\n",
    "            self.dfs(p.right,sum-p.val,tmp+[p.val])\n",
    "            self.dfs(p.left,sum-p.val,tmp+[p.val])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def helper(self, root, sum, curr_path, paths):\n",
    "        \n",
    "        if root == None:\n",
    "            return\n",
    "        \n",
    "        path = curr_path + [root.val]\n",
    "        if root.left == None and root.right == None:\n",
    "            if root.val == sum:\n",
    "                paths.append(path)\n",
    "            return\n",
    "        self.helper(root.left, sum-root.val, path, paths)\n",
    "        self.helper(root.right, sum-root.val, path, paths)\n",
    "    \n",
    "    def pathSum(self, root, sum):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type sum: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        paths = []\n",
    "        path = []\n",
    "        self.helper(root, sum, path, paths)\n",
    "        return paths"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root, sum):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type sum: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        l = []\n",
    "        def preorder(root, sum, p, l):\n",
    "            if root.val==sum and not root.left and not root.right:\n",
    "                p.append(root.val)\n",
    "                l.append(p)\n",
    "            if root.left:\n",
    "                preorder(root.left, sum-root.val, p+[root.val], l)\n",
    "            if root.right:\n",
    "                preorder(root.right, sum-root.val, p+[root.val], l)\n",
    "        \n",
    "        if not root:\n",
    "            return []\n",
    "        preorder(root, sum, [], l)\n",
    "        \n",
    "        return l\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, target: int):\n",
    "        result = []\n",
    "        dfs(root, target, [], result)\n",
    "        return result\n",
    "\n",
    "\n",
    "def dfs(root: TreeNode, target: int, nums: list, result: list):\n",
    "    if root is None:\n",
    "        return\n",
    "    target -= root.val\n",
    "    nums.append(root.val)\n",
    "    if root.left is None and root.right is None and target == 0:\n",
    "        result.append(nums)\n",
    "        return\n",
    "    dfs(root.left, target, nums[:], result)\n",
    "    dfs(root.right, target, nums[:], result)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    " \n",
    "class Solution(object):\n",
    "    \n",
    "    \n",
    "    def pathSum(self, root, sum):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type sum: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        self.res=[]\n",
    "        \n",
    "        def help(root,cursum,tmplist):\n",
    "            if not root:\n",
    "                return\n",
    "            tmplist.append(root.val)\n",
    "            cursum+=root.val\n",
    "            if cursum==sum and not root.left and not root.right:\n",
    "                self.res.append(tmplist)\n",
    "            else:\n",
    "                if root.left:\n",
    "                    help(root.left,cursum,tmplist[:])\n",
    "                if root.right:\n",
    "                    help(root.right,cursum,tmplist[:])\n",
    "                \n",
    "            \n",
    "            \n",
    "            \n",
    "        help(root,0,[])  \n",
    "        return self.res\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root, sum):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type sum: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        def searchList(root, mylist, sum, target):\n",
    "            if root is None :\n",
    "                return None\n",
    "            newSum = root.val + sum\n",
    "            newList = []\n",
    "            newList += mylist\n",
    "            newList.append(root.val)\n",
    "            if (root.left is None) and (root.right is None):\n",
    "                if newSum == target:\n",
    "                    return newList\n",
    "                else:\n",
    "                    return None\n",
    "            else:\n",
    "                retList = []\n",
    "                retLeft = searchList(root.left,newList,newSum,target)\n",
    "                retRight = searchList(root.right,newList,newSum,target)\n",
    "                if retLeft is None:\n",
    "                    retList += []\n",
    "                elif isinstance(retLeft[0],list):\n",
    "                    for i in range(len(retLeft)):\n",
    "                        retList.append(retLeft[i])\n",
    "                else:\n",
    "                    retList.append(retLeft)\n",
    "                if retRight is None:\n",
    "                    retList += []\n",
    "                elif isinstance(retRight[0],list):\n",
    "                    for i in range(len(retRight)):\n",
    "                        retList.append(retRight[i])\n",
    "                else:\n",
    "                    retList.append(retRight)\n",
    "                if len(retList) == 0:\n",
    "                    return None\n",
    "                return retList\n",
    "        ret = searchList(root,[],0,sum)\n",
    "        if ret is None:\n",
    "            return []\n",
    "        elif isinstance(ret[0],int):\n",
    "            return [ret]\n",
    "        else:\n",
    "            return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum_: int) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        stack = [([root.val], root)]\n",
    "        res = []\n",
    "        while stack:\n",
    "            tmp, node = stack.pop()\n",
    "            if not node.right and not node.left and sum(tmp) == sum_:\n",
    "                res.append(tmp)\n",
    "            if node.right:\n",
    "                stack.append((tmp + [node.right.val], node.right))\n",
    "            if node.left:\n",
    "                stack.append((tmp + [node.left.val], node.left))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum_: int) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return None\n",
    "        stack = [([root.val], root)]#栈存储值的列表和节点\n",
    "        res = []\n",
    "        while stack:\n",
    "            tmp, node = stack.pop()\n",
    "            if not node.left and not node.right and sum(tmp) == sum_:\n",
    "                res.append(tmp)\n",
    "            if node.left:\n",
    "                stack.append((tmp + [node.left.val], node.left))\n",
    "            if node.right:\n",
    "                stack.append((tmp + [node.right.val], node.right))\n",
    "        return res\n",
    "\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    \"迭代 O（logn）\"\n",
    "    def pathSum(self, root: TreeNode, sum_: int):\n",
    "        if not root:\n",
    "            return []\n",
    "        stack=[([root.val],root)]\n",
    "        res=[]\n",
    "        while stack:\n",
    "            tmp,node=stack.pop()\n",
    "            if not node.left  and not node.right and sum(tmp)==sum_:\n",
    "                res.append(tmp)\n",
    "            if node.right:\n",
    "                stack.append((tmp+[node.right.val],node.right))\n",
    "            if node.left:\n",
    "                stack.append((tmp+[node.left.val],node.left))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# # Definition for a binary tree node.\n",
    "# # class TreeNode:\n",
    "# #     def __init__(self, x):\n",
    "# #         self.val = x\n",
    "# #         self.left = None\n",
    "# #         self.right = None\n",
    "\n",
    "# class Solution:\n",
    "#     def pathSum(self, root: TreeNode, total: int) -> List[List[int]]:\n",
    "#         ret = list()\n",
    "#         path = list()\n",
    "        \n",
    "#         def dfs(root: TreeNode, total: int):\n",
    "#             if not root:\n",
    "#                 return\n",
    "#             path.append(root.val)\n",
    "#             total -= root.val\n",
    "#             if not root.left and not root.right and total == 0:\n",
    "#                 ret.append(path[:])\n",
    "#             dfs(root.left, total)\n",
    "#             dfs(root.right, total)\n",
    "#             path.pop()\n",
    "        \n",
    "#         dfs(root, total)\n",
    "#         return ret\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, total: int) -> List[List[int]]:\n",
    "        ret = list()\n",
    "        parent = collections.defaultdict(lambda: None)\n",
    "\n",
    "        def getPath(node: TreeNode):\n",
    "            tmp = list()\n",
    "            while node:\n",
    "                tmp.append(node.val)\n",
    "                node = parent[node]\n",
    "            ret.append(tmp[::-1])\n",
    "\n",
    "        if not root:\n",
    "            return ret\n",
    "        \n",
    "        que_node = collections.deque([root])\n",
    "        que_total = collections.deque([0])\n",
    "\n",
    "        while que_node:\n",
    "            node = que_node.popleft()\n",
    "            rec = que_total.popleft() + node.val\n",
    "\n",
    "            if not node.left and not node.right:\n",
    "                if rec == total:\n",
    "                    getPath(node)\n",
    "            else:\n",
    "                if node.left:\n",
    "                    parent[node.left] = node\n",
    "                    que_node.append(node.left)\n",
    "                    que_total.append(rec)\n",
    "                if node.right:\n",
    "                    parent[node.right] = node\n",
    "                    que_node.append(node.right)\n",
    "                    que_total.append(rec)\n",
    "\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:\n",
    "        ret = list()\n",
    "        parent = collections.defaultdict(lambda: None)\n",
    "\n",
    "        if not root:\n",
    "            return ret\n",
    "\n",
    "        def getPath(node: TreeNode):\n",
    "            tmp = list()\n",
    "            while node:\n",
    "                tmp.append(node.val)\n",
    "                node = parent[node]\n",
    "            ret.append(tmp[::-1])\n",
    "\n",
    "        que_node = collections.deque([root])\n",
    "        que_total = collections.deque([0])\n",
    "        while que_node:\n",
    "            node = que_node.popleft()\n",
    "            rec = que_total.popleft() + node.val\n",
    "            if not node.left and not node.right:\n",
    "                if rec == sum:\n",
    "                    getPath(node)\n",
    "            else:\n",
    "                if node.left:\n",
    "                    parent[node.left] = node\n",
    "                    que_node.append(node.left)\n",
    "                    que_total.append(rec)\n",
    "                if node.right:\n",
    "                    parent[node.right] = node\n",
    "                    que_node.append(node.right)\n",
    "                    que_total.append(rec)\n",
    "        return ret\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://leetcode-cn.com/problems/path-sum-ii/\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        if not root.left and not root.right:\n",
    "            return [[sum]] if root.val == sum else []\n",
    "        res = []\n",
    "        cur = collections.deque()\n",
    "        cur.append((root, [root.val], root.val))\n",
    "        while cur:\n",
    "            node, path, path_sum = cur.popleft()\n",
    "            if not node.left and not node.right and path_sum == sum:\n",
    "                res.append(path)                \n",
    "            if node.left:\n",
    "                cur.append((node.left, path + [node.left.val], path_sum + node.left.val))\n",
    "            if node.right:\n",
    "                cur.append((node.right, path + [node.right.val], path_sum + node.right.val))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:\n",
    "        # bfs \n",
    "        from collections import deque\n",
    "        if not root:\n",
    "            return []\n",
    "        res = []\n",
    "        q = deque()\n",
    "        sumc = 0\n",
    "        path = []\n",
    "        q.append((sumc, root, path))\n",
    "        while q:\n",
    "            sumc, node, path = q.popleft()\n",
    "            if sumc + node.val == sum and (not node.left and not node.right):\n",
    "                res.append(path + [node.val])\n",
    "            if node.left:\n",
    "                q.append((sumc + node.val, node.left, path+ [node.val]))\n",
    "            if node.right:\n",
    "                q.append((sumc + node.val, node.right, path+ [node.val]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:\n",
    "        path = []\n",
    "        result = []\n",
    "        \n",
    "        def DFS(node, value):\n",
    "            if not node: #空节点不处理\n",
    "                return\n",
    "            path.append(node.val) #记录路径\n",
    "            value -= node.val #计算剩余数值\n",
    "            if node.left or node.right:  #并非叶子节点\n",
    "                DFS(node.left, value) #左子树\n",
    "                DFS(node.right, value) #右子树\n",
    "            elif value == 0:\n",
    "                result.append(path[:])   #路径和为sum，记录结果\n",
    "            path.pop()      #返回上一个节点\n",
    "\n",
    "        DFS(root,sum)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:\n",
    "        def getpath(root, parent):\n",
    "            path = []\n",
    "            while root:\n",
    "                path.append(root.val)\n",
    "                root = parent[root]\n",
    "            return path[::-1]\n",
    "\n",
    "        if not root: return []\n",
    "        res = []\n",
    "        que_node = collections.deque([root])\n",
    "        que_val = collections.deque([root.val])\n",
    "        parent = {}\n",
    "        parent[root] = None\n",
    "        while que_node:\n",
    "            node = que_node.popleft()\n",
    "            temp = que_val.popleft()\n",
    "            if not node.left and not node.right and temp == targetSum:\n",
    "                res.append(getpath(node, parent))\n",
    "            if node.left: \n",
    "                parent[node.left] = node\n",
    "                que_node.append(node.left)\n",
    "                que_val.append(temp + node.left.val)\n",
    "            if node.right:\n",
    "                parent[node.right] = node\n",
    "                que_node.append(node.right)\n",
    "                que_val.append(temp + node.right.val)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        st=[(root,targetSum,[root.val])]\n",
    "        re=[]\n",
    "        while st:\n",
    "            cur,value,path=st.pop()\n",
    "            if not cur.left and not cur.right and cur.val==value:\n",
    "                re.append(path)\n",
    "            if cur.right:\n",
    "                tmp=path[:]\n",
    "                tmp.append(cur.right.val)\n",
    "                st.append((cur.right,value-cur.val,tmp))\n",
    "            if cur.left:\n",
    "                tmp=path[:]\n",
    "                tmp.append(cur.left.val)\n",
    "                st.append((cur.left,value-cur.val,tmp))\n",
    "        return re\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:\n",
    "        ret = list()\n",
    "        parent = collections.defaultdict(lambda: None)\n",
    "\n",
    "        def getPath(node: TreeNode):\n",
    "            tmp = list()\n",
    "            while node:\n",
    "                tmp.append(node.val)\n",
    "                node = parent[node]\n",
    "            ret.append(tmp[::-1])\n",
    "\n",
    "        if not root:\n",
    "            return ret\n",
    "        \n",
    "        que_node = collections.deque([root])\n",
    "        que_total = collections.deque([0])\n",
    "\n",
    "        while que_node:\n",
    "            node = que_node.popleft()\n",
    "            rec = que_total.popleft() + node.val\n",
    "\n",
    "            if not node.left and not node.right:\n",
    "                if rec == targetSum:\n",
    "                    getPath(node)\n",
    "            else:\n",
    "                if node.left:\n",
    "                    parent[node.left] = node\n",
    "                    que_node.append(node.left)\n",
    "                    que_total.append(rec)\n",
    "                if node.right:\n",
    "                    parent[node.right] = node\n",
    "                    que_node.append(node.right)\n",
    "                    que_total.append(rec)\n",
    "\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        result = []\n",
    "        parent = {root: None}\n",
    "\n",
    "        def addPath(node):\n",
    "            path = collections.deque()\n",
    "            while node:\n",
    "                path.appendleft(node.val)\n",
    "                node = parent[node]\n",
    "            result.append(list(path))\n",
    "            return\n",
    "        \n",
    "        deq = collections.deque([(root, targetSum)])\n",
    "        while deq:\n",
    "            x, val = deq.popleft()\n",
    "            val -= x.val\n",
    "            if not x.left and not x.right and val == 0:\n",
    "                addPath(x)\n",
    "            if x.left:\n",
    "                deq.append((x.left, val))\n",
    "                parent[x.left] = x\n",
    "            if x.right:\n",
    "                deq.append((x.right, val))\n",
    "                parent[x.right] = x\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:\n",
    "    \tresult = []\n",
    "    \tnums = []\n",
    "    \tdef backtrace(root, presum, targetSum):\n",
    "    \t\tif not root:\n",
    "    \t\t\treturn \n",
    "    \t\tnums.append(root.val)\n",
    "    \t\tif not root.left and not root.right and presum + root.val == targetSum:\n",
    "    \t\t\tresult.append(nums[:])\n",
    "    \t\tbacktrace(root.left, presum+root.val, targetSum)\n",
    "    \t\tbacktrace(root.right, presum+root.val, targetSum)\n",
    "    \t\tnums.pop()\n",
    "    \tbacktrace(root, 0, targetSum)\n",
    "    \treturn result\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]:\n",
    "        ret = list()\n",
    "        path = list()\n",
    "        \n",
    "        def dfs(root: TreeNode, targetSum: int):\n",
    "            if not root:\n",
    "                return\n",
    "            path.append(root.val)\n",
    "            targetSum -= root.val\n",
    "            if not root.left and not root.right and targetSum == 0:\n",
    "                ret.append(path[:])\n",
    "            dfs(root.left, targetSum)\n",
    "            dfs(root.right, targetSum)\n",
    "            path.pop()\n",
    "        \n",
    "        dfs(root, targetSum)\n",
    "        return ret\"\"\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:\n",
    "    \tresult = []\n",
    "    \tnums = []\n",
    "    \tdef backtrace(root, nums, presum, targetSum):\n",
    "    \t\tif not root:\n",
    "    \t\t\treturn \n",
    "    \t\tnums.append(root.val)\n",
    "    \t\tif not root.left and not root.right and presum + root.val == targetSum:\n",
    "    \t\t\tresult.append(nums[:])\n",
    "    \t\tbacktrace(root.left, nums, presum+root.val, targetSum)\n",
    "    \t\tbacktrace(root.right, nums, presum+root.val, targetSum)\n",
    "    \t\tnums.pop()\n",
    "    \tbacktrace(root, nums, 0, targetSum)\n",
    "    \treturn result\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]:\n",
    "        ret = list()\n",
    "        path = list()\n",
    "        \n",
    "        def dfs(root: TreeNode, targetSum: int):\n",
    "            if not root:\n",
    "                return\n",
    "            path.append(root.val)\n",
    "            targetSum -= root.val\n",
    "            if not root.left and not root.right and targetSum == 0:\n",
    "                ret.append(path[:])\n",
    "            dfs(root.left, targetSum)\n",
    "            dfs(root.right, targetSum)\n",
    "            path.pop()\n",
    "        \n",
    "        dfs(root, targetSum)\n",
    "        return ret\"\"\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        stack = [(root, [root.val])]\n",
    "        ans = []\n",
    "        while stack:\n",
    "            node, path = stack.pop()\n",
    "            if not node.left and not node.right and sum(path) == targetSum: \n",
    "                ans.append(path)\n",
    "            if node.right:\n",
    "                stack.append((node.right, path + [node.right.val]))\n",
    "            if node.left: \n",
    "                stack.append((node.left, path + [node.left.val]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "\n",
    "        stack = [(root, root.val, [root.val])]\n",
    "        paths = []\n",
    "\n",
    "        while stack:\n",
    "            node, current_sum, path = stack.pop()\n",
    "\n",
    "            if not node.left and not node.right and current_sum == targetSum:\n",
    "                paths.append(path)\n",
    "\n",
    "            if node.right:\n",
    "                stack.append((node.right, current_sum + node.right.val, path + [node.right.val]))\n",
    "\n",
    "            if node.left:\n",
    "                stack.append((node.left, current_sum + node.left.val, path + [node.left.val]))\n",
    "\n",
    "        return paths"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:\n",
    "        result = []\n",
    "        path = []\n",
    "        if not root:\n",
    "            return result\n",
    "\n",
    "        stack = []\n",
    "        stack.append(root)\n",
    "        stack.append(targetSum - root.val)\n",
    "        path.append(root.val)\n",
    "        stack.append(path)\n",
    "\n",
    "        while stack:\n",
    "            tmp_path = stack.pop()\n",
    "            sum_val = stack.pop()\n",
    "            node = stack.pop()\n",
    "\n",
    "            if not node.left and not node.right and sum_val == 0:\n",
    "                result.append(list(tmp_path))\n",
    "\n",
    "            if node.right:\n",
    "                stack.append(node.right)\n",
    "                stack.append(sum_val - node.right.val)\n",
    "                tmp_path.append(node.right.val)\n",
    "                stack.append(list(tmp_path))\n",
    "                tmp_path.pop()\n",
    "\n",
    "            if node.left:\n",
    "                stack.append(node.left)\n",
    "                stack.append(sum_val - node.left.val)\n",
    "                tmp_path.append(node.left.val)\n",
    "                stack.append(list(tmp_path))\n",
    "                tmp_path.pop()\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "\n",
    "        ans_list = []\n",
    "        ans = []\n",
    "        def backtrack(root, targetSum):           \n",
    "            ans.append(root.val)\n",
    "            if root.left:\n",
    "                backtrack(root.left, targetSum - root.val)\n",
    "            if root.right:\n",
    "                backtrack(root.right, targetSum - root.val)\n",
    "            if not root.left and not root.right and targetSum == root.val:\n",
    "                ans_list.append(ans.copy())\n",
    "            ans.pop()\n",
    "\n",
    "        backtrack(root, targetSum)\n",
    "        return ans_list\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        if not root:\n",
    "            return res\n",
    "        path = []\n",
    "        self.traverse(root, targetSum, path, res)\n",
    "        return res\n",
    "        \n",
    "\n",
    "    def traverse(self, root: Optional[TreeNode], targetSum: int, path: List, res: List):\n",
    "        if not root:\n",
    "            return\n",
    "        targetSum -= root.val\n",
    "        path.append(root.val)\n",
    "        if not root.left and not root.right:\n",
    "            if targetSum == 0:\n",
    "                res.append(list(path))\n",
    "                return\n",
    "        if root.left:\n",
    "            self.traverse(root.left, targetSum, path, res)\n",
    "            path.pop()\n",
    "        if root.right:\n",
    "            self.traverse(root.right, targetSum, path, res)\n",
    "            path.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:\n",
    "        def DFSTree(root: TreeNode, path: str, targetSum: int):\n",
    "            if root == None:\n",
    "                return\n",
    "            if root.left == None and root.right == None:\n",
    "                path += str(root.val)\n",
    "                ans = path.split('.')\n",
    "                int_value = [int(x) for x in ans]\n",
    "                if sum(int_value) == targetSum:\n",
    "                    result.append(int_value)               \n",
    "                return\n",
    "            path += str(root.val) + '.'\n",
    "            DFSTree(root.left, path, targetSum)\n",
    "            DFSTree(root.right, path, targetSum)\n",
    "        result = []\n",
    "        DFSTree(root, \"\", targetSum)\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:\n",
    "        def find_path(root,path):\n",
    "            if root:\n",
    "                path+=str(root.val)\n",
    "                # 如果到叶子结点\n",
    "                if not root.left and not root.right:\n",
    "                    paths.append(path)\n",
    "                else:\n",
    "                    path+=\" \"\n",
    "                    find_path(root.left,path)\n",
    "                    find_path(root.right,path)\n",
    "        paths = []\n",
    "        find_path(root,\"\")\n",
    "        # print(paths)\n",
    "        res = []\n",
    "        for path in paths:\n",
    "            tmplst = path.split()\n",
    "            tmplst = [int(x) for x in tmplst]\n",
    "            if sum(tmplst)==targetSum:\n",
    "                res.append(tmplst)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:\n",
    "        paths, path = [], []\n",
    "        print(root)\n",
    "        def dfs(root, tar):\n",
    "            # 异常条件\n",
    "            if not root: return\n",
    "            path.append(root.val)\n",
    "            tar -= root.val\n",
    "            # 结束条件\n",
    "            if not root.left and not root.right and tar == 0:\n",
    "                paths.append(list(path))\n",
    "            dfs(root.left, tar)\n",
    "            dfs(root.right, tar)\n",
    "            path.pop() #?\n",
    "        dfs(root, targetSum)\n",
    "        \n",
    "        return paths\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:\n",
    "        # 自顶向下递归\n",
    "        res=[]\n",
    "        path=[]\n",
    "\n",
    "        @cache\n",
    "        def dfs(root,cursum):\n",
    "            if not root:\n",
    "                return\n",
    "            path.append(root.val)\n",
    "            cursum-=root.val\n",
    "            if  (root.left == root.right) and cursum==0:\n",
    "                res.append(path[:])\n",
    "            dfs(root.left,cursum)\n",
    "            dfs(root.right,cursum)\n",
    "            path.pop()\n",
    "\n",
    "        dfs(root,targetSum)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:\n",
    "        # 自顶向下递归\n",
    "        res=[]\n",
    "        path=[]\n",
    "\n",
    "        @cache\n",
    "        def dfs(root,cursum):\n",
    "            if not root:\n",
    "                return\n",
    "            path.append(root.val)\n",
    "            cursum-=root.val\n",
    "            if  (root.left == root.right) and cursum==0:\n",
    "                res.append(path[:])\n",
    "            dfs(root.left,cursum)\n",
    "            dfs(root.right,cursum)\n",
    "            path.pop()\n",
    "\n",
    "        dfs(root,targetSum)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        def dfs(root, val, l):\n",
    "            if(root is None):\n",
    "                return\n",
    "            if(val+root.val == targetSum and root.left is None and root.right is None):\n",
    "                ans.append(l+[root.val])\n",
    "            else:\n",
    "                dfs(root.left, val+root.val, l+[root.val])\n",
    "                dfs(root.right, val+root.val, l+[root.val])\n",
    "        dfs(root, 0, [])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:\n",
    "        def dfs(ans,summ,root,path):\n",
    "            if root is None:\n",
    "                return\n",
    "            if summ-root.val==0 and root.left is None and root.right is None:\n",
    "                return ans.append(path+[root.val])\n",
    "            dfs(ans,summ-root.val,root.left,path+[root.val])\n",
    "            dfs(ans,summ-root.val,root.right,path+[root.val])\n",
    "        ans=[]\n",
    "        if root is None:\n",
    "            return [] \n",
    "        dfs(ans,targetSum,root,[])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:\n",
    "        ans=[]\n",
    "        def dfs(root,path,target):\n",
    "            if not root: return\n",
    "            if not root.left and not root.right:\n",
    "                if target==root.val:\n",
    "                    \n",
    "                    path += [root.val]\n",
    "                    ans.append(path)\n",
    "                    return\n",
    "            dfs(root.left,path+[root.val],target-root.val)\n",
    "            dfs(root.right,path+[root.val],target-root.val)\n",
    "        dfs(root,[],targetSum)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:\n",
    "        if root is None:\n",
    "            return []\n",
    "        result = []\n",
    "        output = []\n",
    "        path = \"\"\n",
    "        sum_temp = 0\n",
    "        self.TreePaths(root, path, output)\n",
    "        for i in output:\n",
    "            temp = i.split(\"->\")\n",
    "            for j in range(len(temp)):\n",
    "                temp[j] = int(temp[j])           \n",
    "            sum_temp = sum(temp)\n",
    "            if sum_temp == targetSum:\n",
    "                result.append(temp)\n",
    "        return result\n",
    "\n",
    "    def TreePaths(self, root, path, output):\n",
    "        path = path + str(root.val)\n",
    "        if not root.left and not root.right:\n",
    "            output.append(path)\n",
    "\n",
    "        if root.left is not None:\n",
    "            self.TreePaths(root.left, path + \"->\", output)\n",
    "               \n",
    "        if root.right is not None:\n",
    "            self.TreePaths(root.right, path + \"->\", output)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:\n",
    "\n",
    "        routes=[]\n",
    "        route=[]\n",
    "        def search(node,routes,route,target):\n",
    "            if not node:\n",
    "                return\n",
    "            route.append(node.val)\n",
    "            target-=node.val\n",
    "            if not node.left and not node.right:\n",
    "                if target==0:\n",
    "                    routes.append(route)\n",
    "            \n",
    "            search(node.left,routes,route.copy(),target)\n",
    "            search(node.right,routes,route.copy(),target)\n",
    "        \n",
    "        search(root,routes,route,targetSum)\n",
    "\n",
    "        return routes\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    output = []\n",
    "    \n",
    "    def dfs(self, node, target, currentList):\n",
    "        if node:\n",
    "            # currentList.append(node.val)\n",
    "            l = currentList + [node.val]\n",
    "            if not node.left and not node.right:\n",
    "                if target == node.val:\n",
    "                    self.output.append(l)\n",
    "            else: \n",
    "                if node.left:\n",
    "                    self.dfs(node.left, target - node.val, l)\n",
    "                if node.right:\n",
    "                    self.dfs(node.right, target - node.val, l)\n",
    "        \n",
    "\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:\n",
    "        l = []\n",
    "        self.output = []\n",
    "        self.dfs(root, targetSum, l)\n",
    "        return self.output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "\n",
    "        self.ans = []\n",
    "        self.traversal(root, [], targetSum)\n",
    "\n",
    "        return self.ans\n",
    "    \n",
    "    def traversal(self, root, path, count):\n",
    "        # if not root:\n",
    "        #     return \n",
    "        count -= root.val\n",
    "        path = path + [root.val]\n",
    "\n",
    "        if not root.left and not root.right:\n",
    "            if count == 0:\n",
    "                self.ans.append(path)\n",
    "            else:\n",
    "                return \n",
    "        \n",
    "        if root.left:\n",
    "            self.traversal(root.left, path, count)\n",
    "        if root.right:\n",
    "            self.traversal(root.right, path, count)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "class Solution:\r\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:\r\n",
    "        self.res = []\r\n",
    "        if not root:\r\n",
    "            return []\r\n",
    "        self.dfs(root,[],targetSum)\r\n",
    "        return self.res\r\n",
    "    \r\n",
    "    def dfs(self,root,lis,targetSum):\r\n",
    "        tmp = lis + [root.val]\r\n",
    "        if not root.left and not root.right:\r\n",
    "            if sum(tmp) == targetSum:\r\n",
    "                self.res.append(tmp)\r\n",
    "        if root.left:\r\n",
    "            self.dfs(root.left,tmp,targetSum)\r\n",
    "        if root.right:\r\n",
    "            self.dfs(root.right,tmp,targetSum)\r\n",
    "\r\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
